/***尚硅谷Java数据结构与java算法                  ***/
/***https://www.bilibili.com/video/BV1E4411H73v***/
/***马踏棋盘算法            P191                 ***/
/***C++ 实现版本    written by Daniel           ***/

#include <iostream>
#include <vector>
#include <list>
#include <ctime>
#include <memory>
//定义一个棋盘
class ChessBoard
{
public:
    using point=std::pair<int, int>;
    //构造函数
    ChessBoard(int x, int y):xMax(x),yMax(y),isVisited(x*y,false),finished(false)
    {}
    //马踏棋盘算法
    void travel(std::vector<std::vector<int>>& board, int x, int y, int step)
    {
        //假设该步可以走
        board[x][y]=step;
        isVisited[x*yMax+y]=true;
        auto nextSteps=nextPoints(std::make_pair(x,y));
        while (!finished && !nextSteps.empty())
        {
            auto nextStep=nextSteps.front();
            nextSteps.pop_front();
            if (!isVisited[nextStep.first*yMax+nextStep.second]){
                travel(board,nextStep.first,nextStep.second,step+1);
            }
        }
        //
        if (step<(xMax*yMax)&& !finished){
            board[x][y]=0;
            isVisited[x*yMax+y]=false;
        }
        else{
            finished=true;
            // showResult(board);
        }
    }
    /*
    功能：给定一个现在的点，返回下一个点可能位置的列表
    参数：给定现在的点 point
    返回值： 下一个可能点的列表
    */
    std::list<point> nextPoints(point nowPoint)
    {
        std::list<point> resList;
        //需要判断下一个点是否越界
        if ((nowPoint.first - 2) >= 0 && (nowPoint.second - 1) >= 0)
        {
            resList.push_back(std::make_pair(nowPoint.first - 2, nowPoint.second - 1));
        }
        if ((nowPoint.first - 2) >= 0 && (nowPoint.second + 1) < yMax)
        {
            resList.push_back(std::make_pair(nowPoint.first - 2, nowPoint.second + 1));
        }
        if ((nowPoint.first + 2) < xMax && (nowPoint.second - 1) >= 0)
        {
            resList.push_back(std::make_pair(nowPoint.first + 2, nowPoint.second - 1));
        }
        if ((nowPoint.first + 2) < xMax && (nowPoint.second + 1) < yMax)
        {
            resList.push_back(std::make_pair(nowPoint.first + 2, nowPoint.second + 1));
        }
        if ((nowPoint.first - 1) >= 0 && (nowPoint.second - 2) >= 0)
        {
            resList.push_back(std::make_pair(nowPoint.first - 1, nowPoint.second - 2));
        }
        if ((nowPoint.first - 1) >= 0 && (nowPoint.second + 2) < yMax)
        {
            resList.push_back(std::make_pair(nowPoint.first - 1, nowPoint.second + 2));
        }
        if ((nowPoint.first + 1) < xMax && (nowPoint.second - 2) >= 0)
        {
            resList.push_back(std::make_pair(nowPoint.first + 1, nowPoint.second - 2));
        }
        if ((nowPoint.first + 1) < xMax && (nowPoint.second + 2) < yMax)
        {
            resList.push_back(std::make_pair(nowPoint.first + 1, nowPoint.second + 2));
        }
        return resList;
    }

private:
    //标志该位置是否已经被访问过
    std::vector<bool> isVisited;
    //棋盘做上角为(0,0),x向下为正，y向右为正；
    //xMax和yMax分别代表行数和列数
    int xMax;
    int yMax;
    bool finished;
};

int main()
{
    std::cout << "算法开始：" << std::endl;
    auto time_start = time(nullptr);
    std::vector<std::vector<int>> initVec(6,std::vector<int>(6,0));
    std::shared_ptr<ChessBoard> chess=std::make_shared<ChessBoard>(6,6);
    chess->travel(initVec,0,0,1);
    auto time_end = time(nullptr);
    for(const auto& item:initVec){
        for(const auto& item2:item){
            std::cout<<item2<<"\t";
        }
        std::cout<<std::endl;
    }
    std::cout << "用时：" << time_end - time_start << "s" << std::endl;
}